14.5 灰色パケット

ワークスティーリングを用いながらマークスタックをする手法は、分割スレッド数が前もってわかってる場合にしか使えない。

ミューテータが割付けもしたりする場合はわからないので困る。

どのスレッドから仕事を盗めばいいのか という話もある。

どういうタイミングで終了ということかも難しい。

たくさんのパケットを受け渡す方式で負荷分散をしつつ上記の問題も解決する。

各スレッドは入力バケットから仕事を奪って処理して、出力パケットに結果を追加する。

3色抽象化で考えるとどちらも 灰色なので、以下の手法を灰色パケットと呼ぶことにする。

グローバルなプールから各スレッドは仕事のパケットを取ってきて、仕事の後プールに戻す。

出力バケットがいっぱいになった時にプールに戻して新たなパケットをもってくる。

ワークスティーリングは深さ優先、灰色パケットは幅優先みたいな感じがする。

以下の3つのリストがグローバルにある。

空のプール(empty pool)

仕事が半分以下しか積まっていないバケット(harf full pool)

ほとんどいっぱいのバケット(full pool)

入出力のパケットを分離することによって起こるいいこと

プロセッサ間での仕事を均等に分散される

自分の出力パケットを自分で消費するということはあまり起こらない。

これはなぜ？ 何が問題？ むしろキャッシュに載ってて嬉しいまでないのか？

リスト的なデータを処理するときに、子フィールドの処理を積極的に分離することで、全体の負荷分散を向上させている？

灰色バケットはオブジェクトのキューをもっていて、オブジェクトは逐次的に処理される。

灰色パケットでは自然に次にマークされるオブジェクトをプリフェッチできる。

↑ これは何？

code:14-4.py

shared fullPool

shared harlFullPool

shared empyuPool

def getInPacket():

atomic:

inPacket = remove(fullPool)

if isEmpty(inPacket):

atomic:

inPacket = remove(halfFullPool)

if isEmpty(inPacket):

inPacket, outPacket = outPacket, inPacket # 共にキューが空だった時には、自分が積んでいた仕事をする ということか。

return not isEmpty(inPacket)

def testAndMarkSafe(packet):

for each ref in packet:

def getOutPacket():

if isFull(outPacket):

generateWork()

if outPacket == null:

atomic:

outPacket = remove(emptyPool)

if outPacket == null:

atomic:

outPacket = remove(halfFullPool)

if outPacket == null:

if not isFull(inPacket):

inPacket, outPacket = outPacket, inPacket

# 戻り値は使ってないから単に不要なreturnか。

def addOutPacket(ref):

getOutPacket()

if outPacket == null || isFull(outPacket):

dirtyCard(ref) # オーバーフローしている。アルゴリズム14-6の上の最後の段落。

else:

add(outPacket, ref)

これだと同期が必要な時がグローバルなリストから取るときと戻す時だけになる。

CASを使うとノンブロッキングになる(ABAに注意)。

メモリフェンスを入れないといけないタイミングも少ない。

オブジェクトをマークしたりスタックに積んだ後はフェンスはいらない。

パケットのやりとり時だけに必要。

割付ビット

スレッドのスタックを保守的に走査する時に、参照に見えるものが本当に参照かどうか(それっぽい値なだけでないかどうか)を判定する。

これだけじゃなくて、ミューテータとコレクタの同期にも使うっぽい。

割付にはローカルアロケーションバッファ(LAB)を使う。

これがオーバーフローした時にはフェンスを発行してアロケーションバッファ内の全てのオブジェクトに対応する割付bitをsetする。

それによって割付/初期化のためのメモリ書き込みと割付bitのセットの順序を保つ。

つまりLABを新たに取ってきた時に、割付bitを先に立てておくことで、必ずその後に初期化と割付での書き込みが走るようにする？

日本語がムズくてコード読んでる感じだと逆では？ って思ってる……。

他にあと2箇所のフェンスが必要。

追跡処理をしてるスレッドが新しい入力バケットを取ってきた際に、そのバケットの中の全てのオブジェクトがたどって安全かどうかをスレッドローカルなデータ構造に記録する。

割付bitがセットされていれば安全に辿れる。

実際に辿る前にもフェンスを発行する。

安全でないオブジェクトの追跡は後回し。代わりに第3の延期パケットに追加する。

延期パケットはそのうちグローバルなプールに戻される(このプールも実はあるらしい？？)。

割付bitがsetされていない限り追跡されないことが保証される。

追跡処理をしてるスレッドはグローバルなプールに戻す時もフェンスを発行する。

プールに戻す書き込みがパケットへの書き込みを追い越すのを防ぐため。

逆に、入力パケットを取ってくる時は必要無い。

ロードとポインタはデータ依存があり、ほとんどのハードウェアでは正しく実行されるので。(は？)

code:14-5.py

def sequentialAllocate(n):

result = free

newFree = result + n

if newFree <= LAB_Limit: # ローカルアロケーションバッファ

free = newFree

# ここでlabにobjを登録？

return result

# LABオーバーフロー

fence:

for each obj in lab:

allocBit(obj) = true

lab, LAB_Limit = newLab() # これこの順番なのはなぜ……？(サイズがわかっていないから確保後にしかLABのオブジェクトには触れないからか)

if lab == null:

return null # メモリないなった。

sequentialAllocate(n) # labが新しくなってるからいけるかも ということです。

灰色パケットを使うと状態の追跡が楽になる。

それぞれのプールは、中に入ってるパケットの数を持っている。

カウンタはatomicにパケット操作時に更新される。

とはいえ見るタイミングによっては不正確な値になる。

しかし、終了条件は空のバケットの大きさが全てのバケットの数になること。

outPacketがオーバーフローした時

とりあえずマークしておいて、そのオブジェクトを含んでいるカードテーブルをdirtyにしておき、あとでそれを発見したらそのオブジェクトからマークを再開する。

code:14-6.py

def acquireWork():

if isEmpty(inPacket):

if getInPacket():

testAndMarkSafe(inPacket)

fence # なんでここでfenceしている？

def performWork():

for each ref in inPacket:

if safe(ref):

for each fld in Pointers(ref):

child = *fld

if child != null && not inMarked(child):

setMarked(child)

addOutPacket(child)

else:

addDeferredPacket(ref) # 安全でないのであとまわし。

def generateWork():

fence:

add(fullPool, outPacket)

outPacket = null